1. Field of the Invention
The present invention relates to digital image processing and, more particularly, to processing continuous-tone images into halftone images.
2. Description of the Related Art
Digital Halftoning is the process of transforming a continuous-tone image into a binary image that has the illusion of the original continuous-tone image. Error diffusion is one important class of digital halftoning algorithms that renders the continuous-tone images by thresholding their gray levels and distributing the errors due to the thresholding to the neighboring unprocessed pixels. See, R. Ulichney, Digital Halftoning, p. 239, MIT Press, Cambridge, Mass., 1987.
The set of "weights" used to distribute the error when performing error diffusion is called the error diffusion filter. For example, the standard Floyd and Steinberg filter 100 contains four weights, 110, 120, 130 140, applied to diffuse error to pixels neighboring the pixel at location 150, as shown in FIG. 1. See, R. W. Floyd and L. Steinberg, "An Adaptive Algorithm for Spacial Grey Scale," Proc. SID, vol. 17/2, pp. 75-77, 1976.
There are many error diffusion filters reported in the literature. Some other examples are J. F. Jarvis, C. N. Judice and W. H. Ninke, "A Survey of Techniques for the Display of Continuous-tone Pictures on Bilevel Displays," Computer Graphics and Image Processing, vol. 5, pp. 13-40, 1976; P. Stucki, "MECCA--Multiple--error Correcting Computation Algorithm for Bilevel Image Hardcopy Reproduction," Research Report RZ1060, IBM Research Laboratory, Zurich, Switzerland, 1981; R. L. Stevenson and G. R. Arce, "Binary Display of Hexagonally Sampled Continuous-tone Images," J. Opt. Soc. Am. A, vol. 2, no. 7, pp. 1009-1013, 1985; and P. W. Wong, "Adaptive Error Diffuision and its Application in Multiresolution Rendering, IEEE Transactions on Image Processing, vol. 5, pp. 1184-1196, July 1996.
Although there are many different error diffusion halftoning techniques, they all suffer from the common defect that they take a non-trivial amount of time to process a continuous-tone digital image. This is because an error diffusion filter is typically applied sequentially to each pixel within the continuous-tone image.
In the case of color images, the halftone processing time is further increased over that of the gray level halftone processing time. This is because separable error diffusion is usually performed when halftoning a color image. During the separable error diffusion process, the color continuous-tone image is first separated into separate color channels. Separate error diffusion halftones are then formed for each of the color channels. Hence, in the typical case where there are three color channels, separable error diffusion halftoning will take at least three times longer to perform than would be the case if error diffusion were performed on a gray level continuous-tone image having the same number of pixels.
Thus, it can be seen that sequential processing burdens associated with error diffusion halftone imaging techniques impose output speed limits upon halftone image output devices, and hinder the use of these devices in many applications.
Therefore, there is an unresolved need for a technique that can improve error diffusion halftone imaging by reducing the amount of time necessary to perform the halftoning process.